COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.TURN ON "←"
C00015 00003	.REQUIRE "NOTES.PDQ" SOURCE_FILE
C00016 ENDMK
C⊗;
.TURN ON "←";
We should now have sufficient background to examine reasonably
complex and non-trivial problems.  This project is an introduction
to the very important area called %2syntax-directed processes%*.
Syntax-directed techniques are used extensively in compiler construction
(see {yonss(P4)}). We shall begin by applying these techniques to evaluation.

As we said earlier there are alternatives to the call-by-value
evaluation scheme; and as we all know there are alternatives to 
the prefix notation which we  chose to represent function application.

For example, in grade school we all learned infix notation and
its implied precedence relations, say for + and *. Simply because
infix notation is the first representation we see doesn't mean that
it is the most convenient for evaluation either by us or by machine.

Let's take as example the expression:  2+3*5.
The grade school precedence relations say that * takes ⊗→precedence↔←
over +.  That is the expression represents:
2+(3*5) rather than (2+3)*5.
We can also easily write the expression in prefix notation:
+[2;*[3;5]].  Here the precedence of operations
is made explicit. Similar postfix notation (where the operators
follow rather than precede the operands) is easy:
[2;[3;5]*]+.

Why this preoccupation with notation? Well, some notational schemes
lend themselves to mechanical evaluation better than others.
There is a great deal of implied intelligence required in the usual
infix scheme.  We have already  seen one very mechanical method for
evaluating some prefix expressions: the %3value%* function in {yonss(P2)}.

.TURN ON "#";
Consider the postfix notation. We will first claim that since we
know that plus and times are both binary operations, the punctuation,
#],#[, and ;#,# is redundant (this is also true for prefix notation).
Thus the string, 2#3#5#*#+, contains the same information as [2;[3;5]*]+.

A strong point of postfix string notation is
its ease of evaluation.  Using "↓" to point to the current position in the string
and using the "|#...#|"-notation of {yon(P43)} to represent the stack,
 the following is a trace of the evaluation of the above string , 2#3#5#*#+.

.BEGIN VERBATIM GROUP

↓		        ↓		    ↓
2 3 5 * + ,|   |  =>  3 5 * + ,| 2 |  => 5 * + , | 3 |  =>
                                                      | 2 |


↓		 ↓
* + , | 5 |  =>  + , | 15 |  => | 17 |.
      | 3 |           |  2 |
      | 2 |

.END


It is a very simple  task to program this scheme as a LISP %3prog%*.
Similarly, it is quite simple to extend this evaluation scheme to
n-ary operators.

Given an arbitrary arithmetic expression involving constants, and
the binary operations of plus and times, we have a straightforward
mechanical evaluation scheme. It is intuitively clear how to translate
infix expressions into postfix notation.  If we could mechanize this
process then we  would have an algorithm for the evaluation of infix
expressions.  First let's attempt to describe precisely the class
of infix expressions which we  wish to evaluate. The BNF notation
is a good vehicle. Perhaps the following:

.BEGIN TABIT2(20,28) GROUP

\<exp>\::= <exp><binop><exp>
\\::= <integer>

\<binop>\::= + | *    .
.END

There are many things wrong with this attempt at a grammar.  First,
many expressions have more than one possible description or parse tree (the grammar
is said to be ambiguous). Second, this grammar doesn't express our 
usual precedence relations. The next attempt is successful:

.BEGIN TABIT3(20,31,57) GROUP
.P68:

\<exp>\::= <exp> + <term>\(1)
\\::= <term>\(2)

\<term>\::= <term> * <factor>\(3)
\\::= <factor>\(4)

\<factor>\::= ( <exp> )\(5)
\\::= <integer>\(6)
\<integer>\::= 0 | 1 | 2  ....\(7)

.END
For example the (only) parsing of 2+3*5 is:


.BEGIN VERBATIM GROUP
		   <exp>
		     |
	     <exp>  +  <term>
	      |               |
	   <term>     <term>*<factor>
	      |             |           |
	   <factor>  <factor>  <integer>
	       |            |               |
	   <integer>  <integer>      5
	       |           |
	       2          3


.END

Our next step will require a temporary act of faith.  We will show later
that this faith is not ill-placed.

.BEGIN INDENT 0,10;GROUP
Assumption: Given an arbitrary (well-formed) arithmetic expression, e,
of our above class, we can find the left-most well-formed 
subexpression, s, such that s is an instance of the RHS of
one of the rules, (1)-(7). Let e' be the expression 
obtained from e, by replacing the occurrence of the RHS by the
LHS, then our assumption is also applicable to e'.
.END

.BEGIN TABS 5,27,45,66;GROUP;NOFILL;TURN ON "\";
For example, 

\e\s\e'\rule

\  2+3*5\  2\<integer>+3*5\(7)
\<integer>+3*5\<integer>\<factor>+3*5\(6)
\<factor>+3*5\<factor>\<term>+3*5\(4)
\<term>+3*5\<term>\<exp>+3*5\(2)
\<exp>+3*5\3\<exp>+<integer>*5\(7)
\<exp>+<integer>\<integer>\<exp>+<factor>*5\(6)
\<exp>+<factor>*5\<factor>\<exp>+<term>*5\(4)
\<exp>+<term>*5\5\<exp>+<term>*<integer>\(7)
\<exp>+<term>*<integer>\<integer>\<exp>+<term>*<factor>\(6)
\<exp>+<term>*<factor>\<term>*<factor>\<exp>+<term>\(3)
\<exp>+<term>\<exp>+<term>\<exp>\(1)

.END

Let us now associate an action with each of the rules (1)-(7) such
that whenever we apply one of the rule in the above reduction 
technique, we will also execute the corresponding action. We
will also designate an initialization routine which will be
executed at the beginning of the reduction.


.BEGIN TABIT3(5,16,35) GROUP;turn off "←";
Initialization: Let V[0:N] be a vector; and let i be a integer variable, initialized to 0.

\    rule\\    action

\<exp>\::= <exp> + <term>\V(i) ← `+'; i ← i+1;
\\::= <term>\ do nothing

\<term>\::= <term>*<factor>\V(i) ← `*'; i ← i+1;
\\::= <factor>\ do nothing

\<factor>\::= (<exp>)\ do nothing
\\::= <integer>\ do nothing

\<integer>\::= 0 | 1 | 2 |...\V(i) ← 0 | V(i) ← 1 |.... ; i ← i+1;

.END
Again performing the reduction of the expression, 2+3*5, but now
executing the action routines as well we find the  contents of V
will contain the following:

.BEGIN VERBATIM GROUP

	      V: 0 1 2 3 4 5 ...
		  2
		  2 3
		  2 3 5
		  2 3 5 *
		  2 3 5 * +

.END
That is, the postfix form of the arithmetic expression is formed in V.

So combining the two algorithms: infix to postfix translation, and
postfix evaluation we could write an infix evaluator. However we
can go one better. By a simple change to the action routines we can
perform infix evaluation as we reduce (or recognize) the expression.

Initialization: Let V[0:N] be a vector and let i be an integer-valued
variable, initialized to 0.
.BEGIN tabit3(5,16,35); GROUP;TURN OFF "←";

\  rule\\  action

\<exp>\::= <exp>+<term>\V(i-2) ← V(i-1)+V(i-2); i ← i-1;
\\::= <term>\ do nothing

\<term>\::= <term>*<factor>\V(i-2) ← V(i-1)*V(i-2); i ← i-1;
\\::= <factor>\ do nothing

\<factor>\::= (<exp>)\ do nothing
\\::= <integer>\ do nothing

\<integer>\::= 0 | 1 | ...\V(i) ← 0 | V(i) ← 1| ... ; i ← i+1;

.END

When the arithmetic expression has been recognized, V(0) will
contain the value of that expression.

This technique of associating action routines (also called semantic
routines) with the BNF (or syntax) equations is extremely powerful.
Such processes are called syntax-directed.  When we discuss compilation
syntax-directed methods will be used.


.BEGIN TURN ON "←";
←%2Project%*

Write a LISP program to perform infix to postfix translation; and then modify
it to perform infix evaluation.

←%2Project%*

As a further example of syntax-directed processes recall the set
of expressions evaluated by ⊗→%3tgmoaf%1↔←: the five primitives under 
composition of functions, all with constant arguments.
Write syntax equations and action routines to effect the evaluation of
such expressions.
.END
.REQUIRE "NOTES.PDQ" SOURCE_FILE;